Seuraavaksi Martin kiinnitettiin vuoden 1959 lännenelokuvaan Rio Bravo, jonka näyttävään näyttelijäkaartiin kuuluivat muun muassa John Wayne ja Ricky Nelson. Tästä elokuvasta Martin sai erityisen paljon tunnustusta sekä yleisöltä että kriitikoilta suorituskyvystään juopon apulaissheriffin Duden roolista. Rio Bravosta tulikin hänen tunnetuin ja arvostetuin elokuvansa. Ohjaaja Howard Hawksin kertoman mukaan studion johtajat eivät tunnistaneet Martinia roolista.